//== SAGITTARIUS ============================================================================

//== FILEDOC =========================================================================

/** @file reDC.h
  * @brief Derivative classes for regular expressions
  * @details A derivative class is basically a partition of
  * the alphabet based (but not quite equivalent to on the equivalence 
  * classes for a given RE. The derivative function (@ref lex_computeDerivative) 
  * computes the derivative for a given RE once for each set in the DC.
  * The derivatives of the same RE with respect to any character in
  * this set (a member of the DC) are guaranteed to be equivalent 
  * (i.e. the DC implementation is conservative).
  * This saves us from computing the derivative of a RE once for each
  * character in the alphabet.
  * See @ref OwensPaper "Owens et al." for more information
  * 
  * @page OwensPaper "Regular-expression derivatives re-examined"
  * Scott Owens, John Reppy & Aaron Turon <br>
  * Coveres topics on which this code is based. <br>
  */

//== BEGINNING OF CODE ===============================================================

#ifndef __SAGUTTARUIS__REDC__H_
#define __SAGUTTARUIS__REDC__H_

//== INCLUDES ========================================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/re/reCS.h"

#ifdef __cplusplus
extern "C" {
#endif

//-- RE Derivative Classes --

/**
 * @brief Derivative class for a single RE
 */
typedef struct {
    /// @brief The number of charsets in the DC
    uint32 n;
    
    /** @brief The charsets in the DC
     * C99-style flexible array member, except in C89
     * without the "flexibility"
     */
    RE_CharSet* s[1];
} RE_DerivClass;

RE_DerivClass* re_deepcopyDC(const RE_DerivClass* d);
RE_DerivClass* re_shallowcopyDC(const RE_DerivClass* d);

/** @brief Destructor for DCs
 */
void re_destroyDC(RE_DerivClass* d);

/** @brief Special DC
 * @details Create a DC with a single charset: the entire alphabet
 */
RE_DerivClass* re_DCFull();

/** @brief Special DC
 * @details Create a DC with two charsets: @a s and 
 * the complement of @a s
 */
RE_DerivClass* re_DCSingle(const RE_CharSet* s);

/** @brief Combine two DCs conservatively
 * @details Combine two DCs in such a way that characters will be related 
 * in the result only if they are related in both @a p and @a q 
 */
RE_DerivClass* re_DCMesh(const RE_DerivClass* p, const RE_DerivClass* q);

/** @brief Dumps the contents of the DC
 */
void re_writeDC(int fd, const RE_DerivClass* d);

#ifdef __cplusplus
}//extern "C"
#endif

#endif
